# 希尔排序：有点算是插入排序的改进了。他的主要思路是我们首先通过增量的方式进行插入排序，比如每隔3个数组成的子列表进行插入排序。
# 最后进行间隔为1的插入排序，但是因为前面的预排序处理所得数据已经十分接近结果了。最后的插入排序也就更加快速
# 下面这个程序还可能没有那么好理解呢！希尔排序实现起来可能不是很简单的。需要带入仔细了解一下。不过我现在已经理解了(强行理解)
def shellSort(alist):
    sublistcount = len(alist)//2
    while sublistcount > 0:
        for startposition in range(sublistcount):
            gapInsertionSort(alist,startposition,sublistcount)

        print('After increments of size',sublistcount,'The list is',alist)

        sublistcount = sublistcount//2



def gapInsertionSort(alist,start,gap):
    for i in range(start+gap,len(alist),gap):
        currentvalue = alist[i]
        position = i
        # print(position)
        while position>=gap and alist[position-gap]>currentvalue:
            alist[position] = alist[position-gap]
            position = position-gap

        alist[position] = currentvalue


if __name__ == '__main__':
    alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    shellSort(alist)
    print(alist)